#ifndef L4_D202406_H
#define L4_D202406_H
#include <algorithm>
#include <iostream>
using namespace std;

/** Q1 人以群分
 *
 * 输入：
 * 1. n 人数
 * 2. 每个人的活跃度
 *
 * 输出：
 * 1. 内向人群人数
 * 2. 外向人群人数
 * 3. 两群活跃度差值（绝对值）
 *
 * 解题思路：
 * 1. 排序：从小到大
 * 2. 分组策略：二分
 * 3.
 */
void Q1() {
  int n;       // n 人数
  cin >> n;    // 输入人数
  int hyd[n];  // 记录人群活跃度
  for (int i = 0; i < n; i++) {
    cin >> hyd[i];
  }
  // 排序
  sort(hyd, hyd + n);
  // sum_in 内向人群活跃度，sum_out 外向人群活跃度，num_in 内向人数，num_out
  // 外向人数
  int sum_in = 0, sum_out = 0, num_in = n / 2, num_out = n / 2;
  for (int i = 0; i < n / 2; i++) {
    sum_in += hyd[i];
    sum_out += hyd[n - i - 1];
  }
  if (n % 2 == 1) {
    // n/2+1
    sum_out += hyd[n / 2 + 1];
    num_out++;
  }
  // ldev 活跃度差值
  int ldev = sum_out - sum_in;
  // 输出
  cout << "Outgoing #: " << num_out << '\n';
  cout << "Introverted #: " << num_in << '\n';
  cout << "Diff = " << ldev << endl;
}

/** Q2 那就别担心了
 *
 * 输入：
 * 1. n 个命题，m 个推理关系
 * 2. m 个推理关系：a b
 * 3. 待检查的关系：A B
 *
 * 输出：推理路径数量，是否逻辑自洽
 *
 * 解题思路：二维数组 + 递归
 *
 */

// 7 => 1

// 7,4,1
// 7,6,5,2,1
// 7,6,5,3,1
// 3 Yes

//    1 2 3 4 5 6 7
// 1  . 0 0 0 0 0 0
// 2  1 . 0 0 0 0 0
// 3  1 0 . 0 0 0 0
// 4  1 0 0 . 0 0 0
// 5  0 1 1 0 . 0 0
// 6  0 0 0 0 1 . 0
// 7  0 0 0 1 0 1 .
// 4 => 1
struct res2 {
  int count;  // 推理路径的数量
  bool flag;  // 是否自洽
};

res2 resolve2(int start, int end, int matrix[505][505], int n) {
  res2 res = {0, true};
  bool flag = false;
  for (int i = 0; i < n; i++) {
    // 跳过自身
    if (i == start - 1) {
      continue;
    }
    // 存在推理关系
    if (matrix[start - 1][i] == 1) {
      flag = true;
      // 当前命题能直接推出最终命题
      if (i == end - 1) {
        res.count++;
      } else {
        res2 temp = resolve2(i + 1, end, matrix, n);
        res.count += temp.count;
        // 不能自洽
        if (!temp.flag) {
          res.flag = false;
        }
      }
    }
  }
  // 当前命题无法推导任何命题
  if (!flag) {
    res.flag = false;
  }
  return res;
}

void Q2() {
  // 输入
  // 命题个数：n
  // 推理个数：m
  int n, m;
  cin >> n >> m;
  // 二维数组（矩阵）存储推理关系：1 表示推理关系存在，反之为 0
  int matrix[505][505] = {0};  // 初始化矩阵
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    matrix[a - 1][b - 1] = 1;
  }
  int start, end;
  cin >> start >> end;
  // 处理
  res2 res = resolve2(start, end, matrix, n);
  // 输出
  cout << res.count << " " << (res.flag ? "Yes" : "No") << endl;
}

/** Q3 凑零钱
 *
 * 输入：
 * 1. 硬币个数：n
 * 2. 凑钱价格：m
 * 3. 硬币面值：coins[n]
 *
 * 输出：
 * 1. 升序输出硬币面值
 * 2. 若解不唯一，输出最小序列（同样的价值，可以多些硬币，但硬币面值更小）
 * 3. 若无解，输出 No Solution
 *
 * 解题思路：排序+递归
 * n 枚硬币，总共 2^n - 1 种组合
 *
 *
 */
struct res3 {
  int* coins;
  int count;
};
res3 resolve3(int* coins, int n, int m) {
  res3 res = {{0}, 0};
  int coin = *coins;
  if (coin == m) {
    res.coins[0] = coin;
    res.count = 1;
  } else if (coin < m) {
    // 用当前硬币
    res3 use = resolve3(coins + 1, n - 1, m - coin);
    // 不用当前硬币
    res3 nuse = resolve3(coins + 1, n - 1, m);
    if(use.count > nuse.count){}
  }
  return res;
}
void Q3() {
  // 输入
  int n, m;
  cin >> n >> m;
  int coins[n];
  bool selected[n] = {0};
  for (int i = 0; i < n; i++) {
    cin >> coins[i];
  }
  // 处理
  sort(coins, coins + n);  // 排序
  res3 res = resolve3(coins, n, m);
  // 输出
  if (res.count == 0) {
    cout << "No Solution" << endl;
  } else {
    for (int i = 0; i < res.count; i++) {
      cout << res.coins[i] << " ";
    }
    cout << endl;
  }
}

/** Q4 拼题 A 打卡奖励
 *
 * 输入：
 * 1. n 张卷子，m 分钟
 * 2. mi[i] 每张卷子耗时
 * 3. ci[i] 每张卷子得分
 *
 * 输出：
 * 1. 最高得分
 *
 * 解题思路：
 * 1. 做分高且耗时少的卷子
 *
 */
// void Q4() {
//   int n, m;
//   int mi[n], ci[n];
//   for (int i = 0; i < n; i++) {
//     cin >> mi[i];
//   }
//   for (int i = 0; i < n; i++) {
//     cin >> ci[i];
//   }
// }

#endif